package com.lfg.leetcode.leetcode0;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 * <p>
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 * <p>
 * Example:
 * <p>
 * Given nums = [2, 7, 11, 15], target = 9,
 * <p>
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 */
public class No1TwoSum {


    /**
     * 时间复杂度： O(n)
     * 空间复杂度： O(1)
     *
     * @param array
     * @param total
     * @return
     */
    public static int[] twoSum3(int[] array, int total) {
        int[] result = new int[2];
        if (array == null || array.length < 2) {
            return result;
        }

        Map<Integer, Integer> data = new HashMap<Integer, Integer>();
        for (int i = 0; i < array.length; i++) {
            int rest = total - array[i];
            if (data.containsKey(rest)) {

                int otherPosition = -1;
                for (int n = 0; n < array.length; n++) {
                    if(rest == array[n]){
                        otherPosition = n;
                        break;
                    }
                }

                if(rest> array[i]){
                    result[0] = i;
                    result[1] = otherPosition;
                }else{
                    result[1] = i;
                    result[0] = otherPosition;
                }

                return result;
            }
            data.put(array[i], i);
        }
        return result;
    }

    /**
     * 时间复杂度： O(n)
     * 空间复杂度： O(1)
     *
     * @param array
     * @param total
     * @return
     */
    public static int[] twoSum2(int[] array, int total) {
        int[] result = new int[2];
        if (array == null || array.length < 2) {
            return result;
        }
        Map<Integer, Integer> data = new HashMap<Integer, Integer>();
        for (int i = 0; i < array.length; i++) {
            data.put(array[i], i);
        }
        for (int i = 0; i < array.length; i++) {
            int rest = total - array[i];
            if (data.containsKey(rest)) {
                result[0] = array[i];
                result[1] = rest;
                return result;
            }
        }
        return result;
    }

    /**
     * 时间复杂度： n的2次方
     * 空间复杂度： O(1)
     *
     * @param array
     * @param total
     * @return
     */
    public static int[] twoSum1(int[] array, int total) {
        int[] result = new int[2];
        if (array == null || array.length < 2) {
            return result;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (i == j) {
                    continue;
                }
                if (array[i] + array[j] == total) {
                    result[0] = array[i];
                    result[1] = array[j];
                    return result;
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] ret = twoSum3(new int[]{1, 2, 11, 4, 5, 6, 7, 8, 9, 101}, 13);
        for (int i = 0; null != ret && i < ret.length; i++) {
            System.out.print(ret[i] + " - ");
        }
    }
}
